#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;


// version 1
class Solution {
public:
    int GetModNum(int num, int k){
        return (num % k + k) % k;
    }

    int subarraysDivByK(vector<int>& nums, int k) {
        //哈希表中装的是前缀和对k的取模
        unordered_map<int, int> hash;
        hash[0] = 1;
        int sum = 0, ret = 0;

        for(auto& x : nums){
            //dp[i]
            sum += x;

            //判断hash中，是否有值和当前sum % x相等的
            int tmp = GetModNum(sum, k);
            if(hash.count(tmp)) ret += hash[tmp];
            
            //修改哈希
            hash[tmp]++;
        }
        return ret;
    }
};